package weekthree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CourseScheduleII_210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        n = numCourses;
        edges = new ArrayList<>();
        inDeg = new int[n];
        for (int i = 0; i < n; i++) {
            edges.add(new ArrayList<Integer>());
        }
        for (int[] edge : prerequisites) {
            int ai = edge[0];
            int bi = edge[1];
            addEdge(bi, ai);
        }

        return topsort();
    }

    private int[] topsort() {
        //从入度0的点出发
        //bfs需要queue
        int[] learned = new int[n];
        int index = 0;
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) q.offer(i);
        }
        //bfs
        while (!q.isEmpty()) {
            int curr = q.poll();
            learned[index++] = curr;
            //学习curr，可以考虑所有从curr出发的边，去掉约束关系。
            for (int y : edges.get(curr)) {
                inDeg[y]--;
                if (inDeg[y] == 0) {
                    q.offer(y);
                }
            }

        }
        if (index == n)
            return learned;
        else return new int[0];
    }

    private void addEdge(int x, int y) {
        edges.get(x).add(y);
        inDeg[y]++;
    }

    private int n;
    private List<List<Integer>> edges;
    //入度数组
    private int[] inDeg;
}
